Information transmitted over, or stored in, a physical medium is susceptible to errors derived from noise and other random processes. Forward error correction (“FEC”) is commonly used to improve the bit error rate (“BER”) of a communications system. A popular FEC implementation is Reed-Solomon error correction.
A Reed-Solomon error correcting code is also a type of erasure code; that is, bits or values of the received code can be marked as erasures, or error locations known in advance, for the purpose of decoding. While a Reed-Solomon code can correct a certain number of errors, it can correct more erasures. Therefore, if the locations of likely errors are known, then the errors can be marked as erasures, increasing the number of errors that can be corrected.
Specifically, a Reed-Solomon code comprises parameters N, k and m. Each Reed-Solomon codeword consists of N symbols, with each symbol consisting of m bits. The codeword contains k symbols of message data, implying that k<N and that the codeword contains N−k symbols of check or parity data.
It is a defining property of a Reed-Solomon code that the decoder can correct up to N−k/2 symbols in error and detect up to N−k symbols in error. It is yet another property of the code that the decoder can correct up to N−k erasure symbols. Further, a decoder can correct a codeword with A errored symbols and B erased symbols as long as 2A+B≦N−k. Hence, the BER of a received information stream can be improved if the decoder can glean additional information about the locations of errored symbols and mark those symbols as erasures.
A Reed-Solomon decoder that does not take advantage of erasures operates akin to a hard-decision FEC decoder. Hard bits are either 0s or 1s at the input of the decoder. Thus, a hard-decision Reed-Solomon decoder can only correct up to N−k/2 symbols in error.
A classical Reed-Solomon decoder, shown in FIG. 1, comprises three processing stages: a syndrome former, a Berlekamp-Massey (BM) decoder, and an error correction unit. The syndrome former generates syndrome values from the received message. The syndrome values are non-zero if the received message contains errors. The Berlekamp-Massey algorithm uses the syndromes to determine the locations of the errors in the received message. Finally, the error correction unit corrects the identified errors. In the case of a binary message, the error correction is a trivial bit flip; in the general case, an appropriate algorithm, such as the Forney algorithm, generates the error values used for error correction.
A soft-decision Reed-Solomon decoder “softens” the input data by marking likely error locations with erasures. Advances in soft-decision Reed-Solomon decoding can lead to improved BER over known decoding techniques, up to a theoretical BER ceiling defined by the N−k maximum number of correctable erasures.
One known method of soft-decision Reed-Solomon decoding makes use of soft-decision information at the bit-level rather than only at the byte-level (or symbol-level). A Reed-Solomon code is beneficial in a noisy channel that manifests bursts of bit errors. Since the bit errors are localized to one or a few symbols, most codewords are correctable. However, in a memoryless noisy channel that only manifests evenly distributed bit errors, the BER of the conventional Reed-Solomon decoder suffers. This method performs bit-level soft-decision decoding by generating, at the encoder, a linear mapping of a string of bits from a number of symbols. The encoder chooses a recursive generator matrix over a Galois Field of size NI that interleaves the m bits of each symbol evenly over m codewords. Thus, each symbol is mapped to a coset of bits and each coset is over a Galois Field of size m, ensuring that decisions are bit-level. The decoder applies a maximum likelihood decoding algorithm (soft-decision decoding) first to the received codeword, which comprises interleaved bits, and then to the coset of interleaved bits forming a transmitted symbol.
Another known method of soft-decision Reed-Solomon decoding uses a list decoding algorithm to improve the number of errors that can be corrected in a codeword. A list decoding algorithm produces a list of potential valid received codewords. Using side information, the soft-decision decoder can prune the list of codewords. The Guruswami-Sudan algorithm can correct n−√{square root over (nk)} errors and comprises two main steps: interpolating a bivariate polynomial from a list of points corresponding to the received word; and factoring the bivariate polynomial to determine the list of codewords corresponding to these factors. The Koetter-Vardy algorithm extends the Guruswami-Sudan list decoding method so that the decoder is a soft-decision decoder. The Koetter-Vardy “front-end” algorithm translates side-information into multiplicities proportional to the reliability of the points; therefore, the bivariate polynomial is found through a biased interpolation with unequal multiplicities. This biased bivariate interpolation polynomial factors to produce a reduced list of codewords.
Both of these soft-decision decoding methods are relatively complex. The complexity is reflected in the hardware implementation of these methods, which leads to higher power consumption. It is therefore desirable to provide an improved soft-decision Reed-Solomon decoder with a relatively low area and power consumption.